%%%----------------------------------------------------------
\chapter{Detecting a line in an image}
%%%----------------------------------------------------------
\label{cha:line}
\section{Problem}
The first part of this assignment is the implementation of algebraic lines. The second part is the detection of lines. Given is a binary image (see figure \ref{fig:02_line1}), which contains of pixels which are roughly aligned to a straight line. An algorithm which calculates the line between this point should be implemented.

\begin{figure}
	\centering
	\includegraphics[width=.5\textwidth]{02_line1}
	\caption{Initial test image of assignment 2}
	\label{fig:02_line1}
\end{figure}


\section{Solution}
The class AlgebraicLine will have multiple constructors like \textbf{AlgebraicLine(double A, double B, double C)}, one with the start and endpoint and one with a set of points. The set of points constructor is using the Eigenvector and the Eigenvalue to calculate the Algebraic line.

The \textit{Total least square} method is a very good solution to calculate the distance to the line:
\begin{equation}
BestFit(x_{i},y_{i}) = \sum_{i} (ax_{i} + by_{i} + c)^{2}
\end{equation}

The \textit{Total least square} doesn't consider the line orientation in the coordinate system, like the \textit{Least squares}. The formula from above can be expressed in a matrix-notation, which than is an Eigenvalue-problem:
\begin{equation}
	\begin{pmatrix}
		\overline{xx} - \overline{x}^2 & \overline{xy} - \overline{x} \cdot \overline{y}\\ 
		\overline{xy} - \overline{x} \cdot \overline{y} & \overline{yy} - \overline{y}^2
	\end{pmatrix}
	\cdot 
	\begin{pmatrix}
		A\\B 
	\end{pmatrix}te
	= \mu
	\begin{pmatrix}
		A\\B 
	\end{pmatrix}
\label{eq:matrix}
\end{equation} 

The solution of this eigen problem has two results of an eigenvector and an eigenvalue. The pair with the smaller eigenvalue is the orthogonal vector of the best fitted line.


\section{Implementation}
\subsection{AlgebraicLine.java}
At first the \textbf{Algebraic Line} class is implemented to store the line parameters and to draw this stored line. In this class we have three constructors:
\subsubsection{public AlgebraicLine(double A, double B, double C)}
This constructor is the simple one where the final line data is stored.
\subsubsection{public AlgebraicLine(Point2D P1, Point2D P2)}
Here we have to calculate the parameters with the following equations:
\begin{equation}
	\begin{array}
		{rcl}
			k & = & \dfrac{P2_y - P1_y}{P2_x - P1_x} \\
			n &=& P1_y - k * P1_x \\
			A &=& -k \\
			B &=& -n \\	
			C &=& 1 
	\end{array}
\end{equation}
\subsubsection{public AlgebraicLine(List<Point> points)}
A constructor which calculates the line parameters of a list of points using the  equation \ref{eq:matrix} to solve the eigen problem and to get the parameters for A, B and C.

\subsubsection{Other methods}
This class also has three functions for normalizing line, calculating the distance between a point and the line and an intersection between to lines. The draw method draws the line onto an image with a given color.

\subsection{A02\_Find\_Algebraic\_Line.java}
This java file is an ImageJ PulgInFilter which finds a line in an binary image. This plugin can handle 8 bin grayscale images and also color images. At first the image gets duplicated for calculation into a Binary image and into a color image.

By searching over all pixels in the image we store all pixels with a higher value than 0. From this points then we calculate the Algebraic Line with the eigen solver. Finally the line gets drawn into the color image and the parameters A, B and C gets logged to the ImageJ console. Also the overall error of all points gets calculated and logged.

\section{Result}
This plugin is capable fitting lines to the test images. In figure you can see the parameters of this lines and the overall errors. An exception is thrown if the line has 0 for parameter A and B. This algorithm is not capable of filtering noise, one idea to reduce noise is to calculate a line out of all points. Than you delete all points that are to far away from the line and with the rest of the points you calculate the resulting line.
\begin{figure}
\centering
    \begin{tabular}{| l || r | r | r |}
    \hline
    & line-test-02 & line-test-03 & line-test-04 \\ \hline \hline
    $A$ & -0.6507 & 0.6395 & 0.4646 \\ \hline
    $B$ & -0.7593 & -0.7688 & -0.8855 \\ \hline
    $C$ & 157.1629 & -8.0474 & 12.9928 \\ \hline \hline
    $\Sigma_{error}$ & 81.9961 & 197.2429 & 18.2064 \\
    \hline
    \end{tabular}
\caption{Result values for the test images. $a$, $b$ and $c$ are the normalized algebraic line parameters. $\Sigma_{error}$ is the sum of all point distances to the line and therefore the total error of the algorithm.}
\label{fig:numbers}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=.75\textwidth]{02_line-test-1}
	\includegraphics[width=.75\textwidth]{02_line-test-2}
	\includegraphics[width=.75\textwidth]{02_line-test-3}
	\caption{Result images with fitted lines.}
	\label{fig:linetest2}
\end{figure}
